package Offer;

public class Test38 
{

	public static void main(String[] args) 
	{
		int[] array={1,2,3,3,3,3,4,5};
		System.out.println(getNumberOfK(array,3));

	}
    public static int getNumberOfK(int[] array,int k)
    {
    	if(array==null||array.length==0)
    		return 0;
    	int number=0;
		int first=getFirstK(array,0,array.length-1,k);
		int last=getLastK(array,0,array.length-1,k);
		if(first>-1&&last>-1)
		{
    		number=last-first+1;
    	}
		return number;
    }
    public static int getFirstK(int[] array,int start,int end,int k)
    {
    	if(start>end)
    		return -1;
    	int mid=(start+end)/2;
    	if(array[mid]==k)
    	{
    		if(mid!=0&&array[mid-1]!=k||mid==0)
    		{
    			return mid;
    		}
    		else
			{
			    end=mid-1;
			}
    	}
    	else if(array[mid]>k)
    	{
    		end=mid-1;
    	}
    	else
    	{
    		start=mid+1;
    	}
    	return getFirstK(array,start,end,k);
    }
    public static int getLastK(int[] array,int start,int end,int k)
    {
    	if(start>end)
    		return -1;
    	int mid=(start+end)/2;
    	if(array[mid]==k)
    	{
    		if(mid<array.length-1&&array[mid+1]!=k||mid==array.length-1)
    		{
    			return mid;
    		}
    		else
    		{
    			start=mid+1;
    		}
    			
    	}
    	else if(array[mid]<k)
    	{
    		start=mid+1;
    	}
    	else
    	{
    		end=mid-1;
    	}
    	return getLastK(array,start,end,k);
    }
}
